#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
#include <string>
using namespace std;

void map_test1()
{
  map<string, string> dict;
  pair<string, string> kv1("sort", "排序");
  dict.insert(kv1);
  dict.insert(pair<string, string>("left", "左"));
  dict.insert(make_pair("right", "右"));
  map<string, string>::iterator it = dict.begin();
  while (it != dict.end())
  {
    cout << it->first << ":" << it->second << endl;
    it++;
  }
  cout << endl;
  for (auto& kv : dict)
  {
    cout << kv.first << ":" << kv.second << endl;
  }
  cout << endl;
}

void map_test2()
{
  string arr[] = {"苹果" , "香蕉", "菠萝", "桃子", "苹果", "菠萝", "苹果"};
  map<string, int> count_map;
  //方法一:find + insert
  //for (auto fruit : arr)
  //{
  //  auto ret = count_map.find(fruit);
  //  if (ret == count_map.end())
  //  {
  //    count_map.insert(make_pair(fruit, 1));
  //  }
  //  else 
  //  {
  //    ret->second++;
  //  }
  //}
  //方法二:insert + 使用insert的返回值
  //for (auto fruit : arr)
  //{
  //  auto ret = count_map.insert(make_pair(fruit, 1));
  //  if (ret.second == false)
  //  {
  //    (ret.first)->second++;
  //  }
  //}
  //方法三：operator[]
  for (auto& fruit : arr)
  {
    count_map[fruit]++;
  }
  //operaotp[]解释
  //mapped_type& operator[] (const key_type& k)
  //{ return (this->insert(make_pair(k, mapped_type())).first->second); }
  //mapped_type()就是临时对象，也就是调用默认构造出来的mapped_type类型的临时对象
  //若key==k的结点存在，返回此节点value的引用
  //若key==k的结点不存在，创建key==k的结点，并将此节点的value初始化为mapped_type(),并返回此结点val的引用
  //operatorp[]的功能 1.插入key==k的结点 2.查找key==k的结点的val 3.修改key==k的结点的val
  count_map["樱桃"];                                    //插入
  count_map["樱桃"] = 3;                                //修改  等价与 count_map.insert(makepair("樱桃", 3)); 插入 + 修改
  cout << "樱桃" << ":" << count_map["樱桃"] << endl;   //查找
  for (auto& e : count_map)
  {
    cout << e.first << ":" << e.second << endl; 
  }
  cout << endl;
  //multimap 没有operatorp[], 与 map的区别就是不管key在不在都插入，允许冗余
  //count(key_type k)函数可以帮助multimap查找有多少个相同key的结点
}

struct Compare 
{
  bool operator()(const map<string, int>::iterator m1, const map<string, int>::iterator m2)
  {
    return m1->second > m2->second;
  }
};

struct Compare_priority_max
{
  bool operator()(map<string, int>::iterator l, map<string, int>::iterator r)
  {
    //小于建大堆，大于建小堆
    return l->second < r->second;
  }

};

void GetFavoriteFruit(const vector<string>& fruits, size_t k)
{
  //仿函数，用于方法一sort 的 Compare条件
  Compare comp;
  map<string, int> count_map;
  for (auto str : fruits)
  {
    count_map[str]++;
  }
  //方法一:将map的迭代器放入vector进行快排
  //vector<map<string, int>::iterator> v;
  //map<string, int>::iterator it = count_map.begin();
  //while (it != count_map.end())
  //{
  //  v.push_back(it);
  //  it++;
  //}
  //sort(v.begin(), v.end(), comp);
  //for (size_t i = 0; i < k; i++)
  //{
  //  cout << v[i]->first << ":" << v[i]->second << endl;
  //}
  //cout << endl;
  //方法二:使用搜索树
  //multimap<int, string> max_tree;
  //for (auto fruit : count_map)
  //{
  //  max_tree.insert(make_pair(fruit.second, fruit.first));
  //}
  //auto max = max_tree.rbegin();
  //for (size_t i = 0; i < k; i++)
  //{
  //  cout << max->second << ":" << max->first << endl;
  //  max++;
  //}
  //cout << endl;
  //
  //方法三:使用优先级队列
  priority_queue<map<string, int>::iterator, vector<map<string,int>::iterator>, Compare_priority_max> sort_queue;
  map<string, int>::iterator it = count_map.begin();
  while (it != count_map.end())
  {
    sort_queue.push(it);
    it++;
  }
  for (size_t i = 0; i < k; i++)
  {
    cout << sort_queue.top()->first << ":" << sort_queue.top()->second << endl;
    sort_queue.pop();
  }
  cout << endl;
  
}
void map_test3()
{
  vector<string> arr = {"苹果" , "香蕉", "菠萝", "桃子", "苹果", "菠萝", "苹果", "樱桃", "苹果", "香蕉"};
  GetFavoriteFruit(arr, 3);
}

int main()
{
  //map_test1();
  //map_test2();
  map_test3();
  return 0;
}
